/**
 * Created by forcht on 2018/5/19.
 */
public class Solution {
    public int sqrt(int x) {
        if (x<2)return x;
        long left=0;
        long right=x/2;
        long last_mid=x;
        while (left<=right){
            long mid=left+(right-left)/2;
            if (mid*mid>x){
                right=mid-1;
            } else if(mid*mid<x){
                left=mid+1;
                last_mid=mid;
            }else {
                return (int)mid;
            }
        }
        return (int)last_mid;
    }
}
